#include <stdio.h>
#include "vm/frame.h"
#include "threads/pte.h"
#include "threads/init.h"
#include "threads/thread.h"
#include "threads/malloc.h"
#include "threads/palloc.h"
#include "userprog/pagedir.h"

//frame table
struct list frame_list;
struct lock frame_list_lock;
static struct frame_struct *eviction_candidate = NULL;

//initializes the supplementary page table and the frame list
void
supplementary_page_table_init (void)
{
  list_init (&frame_list);  
  lock_init (&frame_list_lock);
}

/*Given a page directory and a virtual address, this method returns
the page entry if it exists, else returns NULL*/
uint32_t *
supplementary_page_table_page_entry_find (uint32_t * page_directory,
                                          const void *virtual_address)
{
  uint32_t *page_table;
  uint32_t *page_directory_entry = page_directory 
                                   + pd_no (virtual_address);
  //no entry in page directory entry, return null
  if (0 == *page_directory_entry)
    return NULL;

  //found a valid page directory entry, hence return the page table entry
  page_table = pde_get_pt(*page_directory_entry);
  return &page_table[pt_no (virtual_address)];
}

/*Given a page directory and a virtual address, this method returns
the newly created page table entry*/
uint32_t *
supplementary_page_table_page_entry_create (uint32_t *page_directory,
                                            const void *virtual_address)
{
  uint32_t *page_table, *page_directory_entry;
  //null page directory passed, hence return NULL
  if (NULL == page_directory)
    return NULL;
  page_directory_entry = page_directory + pd_no (virtual_address);
  if (0 == *page_directory_entry)
    { //empty page directory entry, hence create
      page_table = palloc_get_page (PAL_ZERO);
      if (NULL == page_table)
        return NULL;
      *page_directory_entry = pde_create (page_table);
    }
  //return the page table entry corresponding to the page directory entry
  page_table = pde_get_pt (*page_directory_entry);
  return &page_table[pt_no (virtual_address)];
}

/*Given a page table entry, this method returns the page struct from
the supplemental page table*/
struct page_struct *
supplementary_page_table_page_struct_lookup (uint32_t *page_table_entry)
{
  struct page_struct page_struct;
  struct page_struct *return_page_struct = NULL;
  struct hash_elem *e                    = NULL;
  struct thread *cur     = thread_current ();
  struct lock *hash_lock = &cur->supplementary_page_table_lock;
  struct hash *hash      = &cur->supplementary_page_table;
  
  //populate data in the lookup page struct
  page_struct.key = (int) page_table_entry;
  lock_acquire (hash_lock);
  e = hash_find (hash, &page_struct.elem);
  lock_release (hash_lock);
  
  //return page struct if found, else return NULL
  if (NULL != e)
    return_page_struct = hash_entry (e, struct page_struct, elem);
  
  return return_page_struct;
}

/*Given all the information, this method adds an entry to the supplemental
page table*/
struct page_struct *
supplementary_page_table_add (uint32_t *page_directory, 
                              uint8_t *user_page, 
                              uint8_t *virtual_address, 
                              size_t page_length, 
                              uint32_t flag, 
                              block_sector_t sector_number,
                              bool writable)
{
  //find the pte
  uint32_t *page_table_entry = 
    supplementary_page_table_page_entry_create (page_directory, user_page);

  //allocate the page struct
  struct page_struct *page_struct = 
    (struct page_struct *) malloc (sizeof (struct page_struct));
  
  //could not allocate page struct, hence return NULL
  if(NULL == page_struct)
    return NULL;

  //fill in the pte info
  page_struct->key = (uint32_t) page_table_entry;
  page_struct->fs = malloc (sizeof (struct frame_struct));

  //could not allocate frame struct, hence return NULL
  if(NULL == page_struct->fs)
    {
      free (page_struct);
      return NULL;
    }
  
  lock_init (&page_struct->fs->frame_lock);
  lock_acquire (&page_struct->fs->frame_lock);

  page_struct->fs->upage = user_page;
  page_struct->fs->vaddr = virtual_address;
  page_struct->fs->page_length = page_length;
  page_struct->fs->flag = flag;
  page_struct->fs->writable = writable;
  page_struct->fs->sector_number = sector_number;
  lock_release (&page_struct->fs->frame_lock);

  //push in supplemental page table
  lock_acquire (&thread_current ()->supplementary_page_table_lock);
  hash_insert (&thread_current ()->supplementary_page_table, 
               &page_struct->elem);
  lock_release (&thread_current ()->supplementary_page_table_lock);
  
  //push back in frame list
  lock_acquire (&frame_list_lock);
  list_push_back (&frame_list, 
                  &page_struct->fs->elem);
  lock_release (&frame_list_lock);

  return page_struct;
}

//given a pte, this method deletes it from the supp_pt
bool
supplementary_page_table_delete (uint32_t *page_table_entry)
{
  struct page_struct *page_struct = 
      supplementary_page_table_page_struct_lookup (page_table_entry);
  
  //could not find entry in the supplemental page table
  if(NULL == page_struct)
    return false;

  lock_acquire (&frame_list_lock);
  list_remove (&page_struct->fs->elem);
  lock_release (&frame_list_lock);

  lock_acquire (&thread_current ()->supplementary_page_table_lock);
  hash_delete (&thread_current ()->supplementary_page_table, &page_struct->elem);
  lock_release (&thread_current ()->supplementary_page_table_lock);

  return true;
}


//hash function to organize the hash table
unsigned
supplementary_page_table_hash_function (const struct hash_elem *elem, 
                                        void *aux UNUSED)
{
  struct page_struct *page_struct = hash_entry (elem, struct page_struct, elem);
  return hash_int ((int)page_struct->key);
}

//comparator function to compare two elements in the hash
bool
supplementary_page_table_comparator_function (const struct hash_elem *first, 
                                              const struct hash_elem *second, 
                                              void *aux UNUSED)
{
  struct page_struct *pfirst = hash_entry (first, struct page_struct, elem);
  struct page_struct *psecond = hash_entry (second, struct page_struct, elem);
  return pfirst->key < psecond->key;  
}

/*Given all the information, the method adds an entry to the supplemental page
table */
bool
add_page (uint8_t *upage, 
          uint8_t *addr, 
          size_t length, 
          uint32_t flag, 
          block_sector_t sector_no,
          bool writable)
{
  if (NULL != pagedir_get_page (thread_current ()->pagedir, upage))
    return false;  

  struct page_struct *page_struct = 
      supplementary_page_table_add (thread_current ()->pagedir, upage, addr, 
                                    length, flag, sector_no, writable);
  return (NULL != page_struct);
}

/*evict a frame from the frame list*/
uint8_t *
supplementary_page_table_frame_evict (void)
{
  struct list_elem *e = NULL;
  uint8_t *virtual_address = NULL;
  struct frame_struct *actual_eviction_frame = NULL;
  //mark the first candidate for eviction if the eviction candidate is NULL
  //  one time initialization, after that the loop moves circularly
  if (NULL == eviction_candidate)
    {
      lock_acquire (&frame_list_lock);
      eviction_candidate = list_entry (list_begin (&frame_list), 
				                               struct frame_struct, 
				                               elem);
      lock_release (&frame_list_lock);
      e = &eviction_candidate->elem;
    }
  int count = 0;
  while (1)
    {

      lock_acquire (&frame_list_lock);
      e = list_next (&eviction_candidate->elem);
      if (e == list_end (&frame_list))
        e = list_begin (&frame_list);
      
       
      eviction_candidate = list_entry (e, struct frame_struct, elem);
      actual_eviction_frame = eviction_candidate;
      
      if ( 0 == count % list_size (&frame_list))
        break;

      //if unable to acquire the frame lock for the currnt frame, move onto the
      //  next frame 
      if (false == lock_try_acquire (&actual_eviction_frame->frame_lock))
        continue;
      
      //evict only memory frames     
      if (actual_eviction_frame->flag == MEMORY)
        {
          bool retVal = false;
          //clear the accessed bit and flush the page dir
          if (pagedir_is_accessed (thread_current ()->pagedir, 
				                           actual_eviction_frame->vaddr))
            {
              retVal = true;
              pagedir_set_accessed (thread_current ()->pagedir, 
				                            actual_eviction_frame->vaddr, false);
              continue;
            }
            else {
              retVal = true;
              pagedir_set_accessed (thread_current ()->pagedir,
                                    actual_eviction_frame->vaddr, false);
              pagedir_clear_page (thread_current ()->pagedir, 
				                          actual_eviction_frame->upage);
              break;
            }     
        }
      
      //release the lock if currently held
      if (true ==
               lock_held_by_current_thread (&actual_eviction_frame->frame_lock))
        lock_release (&actual_eviction_frame->frame_lock);
      lock_release (&frame_list_lock);
    }
    
    //return the virtual address to be used
    virtual_address = actual_eviction_frame->vaddr;
    swap_out (actual_eviction_frame);
    return virtual_address;
}
